package someTestExcemple.huaweiOd.dp.dp01;

//01背包问题
import java.util.*;
//0 - 1 背包问题简介
//        0 - 1 背包问题是一个经典的组合优化问题。
//        假设有一个容量为 W 的背包和 n 个物品，每个物品有对应的重量 w[i] 和价值 v[i]。
//        你需要在不超过背包容量的前提下，选择部分物品放入背包，使得背包内物品的总价值最大。
//        每个物品只能选择放入（1）或者不放入（0）背包，不能只放入部分。
//        动态规划算法思路
//        1. 定义状态
//        设 dp[i][j] 表示前 i 个物品放入容量为 j 的背包中所能获得的最大价值。
//        这里的 i 范围是从 0 到 n，j 范围是从 0 到 W。
//        2. 初始化状态
//        当 i = 0 时，即没有物品可放，无论背包容量 j 为多少，dp[0][j] = 0。
//        当 j = 0 时，即背包容量为 0，无论有多少物品，dp[i][0] = 0。
//        3. 状态转移方程
//        对于第 i 个物品，有两种情况：
//        不放入背包：此时 dp[i][j] 等于前 i - 1 个物品放入容量为 j 的背包的最大价值，即 dp[i][j] = dp[i - 1][j]。
//        放入背包：前提是当前背包容量 j 大于等于第 i 个物品的重量 w[i - 1]（注意数组下标从 0 开始）。放入后，dp[i][j] 等于前 i - 1 个物品放入容量为 j - w[i - 1] 的背包的最大价值加上第 i 个物品的价值 v[i - 1]，即 dp[i][j] = dp[i - 1][j - w[i - 1]] + v[i - 1]。
//        综合这两种情况，状态转移方程为：
//        plaintext
//        if j < w[i - 1]:
//        dp[i][j] = dp[i - 1][j]
//        else:
//        dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i - 1]] + v[i - 1])
//
//        4. 最终结果
//        最终的最大价值存储在 dp[n][W] 中，其中 n 是物品的数量，W 是背包的容量。
public class Backpack01 {
    public static int knapsack(int[] weights, int[] values, int capacity) {
        int n = weights.length;
        // 创建二维数组 dp 来保存子问题的解
        int[][] dp = new int[n + 1][capacity + 1]; //0号位不用的

        // 初始化状态
        for (int i = 0; i <= n; i++) {
            dp[i][0] = 0;
        }
        for (int j = 0; j <= capacity; j++) {
            dp[0][j] = 0;
        }

        // 填充 dp 数组
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= capacity; j++) {
                if (j < weights[i - 1]) {
                    // 当前背包容量不足以放入第 i 个物品
                    dp[i][j] = dp[i - 1][j];
                } else {
                    // 选择放入或不放入第 i 个物品中的最大值
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weights[i - 1]] + values[i - 1]);
                }
            }
        }

        // 返回最终结果
        return dp[n][capacity];
    }

    public static void main(String[] args) {
        int[] weights = {2, 3, 4, 5};
        int[] values = {3, 4, 5, 6};
        int capacity = 8;
        int maxValue = knapsack(weights, values, capacity);
        System.out.println("背包能装下的最大价值是: " + maxValue);
    }
}
